package pers.tz.题目;

import pers.tz.common.TreeNode;
import pers.tz.common.TreeUtils;

import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 提供一个二叉树，判断其是否是满二叉树
 * 满二叉树的定义：节点数 = 2^树高 - 1
 *
 * @author irony
 * @date 2024-03-13
 */
public class 满二叉树 {
    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(1);
        TreeNode t2 = new TreeNode(1);
        TreeNode t3 = new TreeNode(1);
        TreeNode t4 = new TreeNode(1);
        TreeNode t5 = new TreeNode(1);
        TreeNode t6 = new TreeNode(1);
        TreeNode t7 = new TreeNode(1);

        t1.left = t2;
        t1.right = t3;
        t2.left = t4;
        t2.right = t5;
        t3.left = t6;
//        t3.right = t7;

        System.out.println(isFullBinaryTree(t1));
    }

    public static boolean isFullBinaryTree(TreeNode root) {
        return process(root).full;
    }

    public static Info process(TreeNode root) {
        if (root == null) {
            return new Info(true, 0, 0);
        }

        Info left = process(root.left);
        Info right = process(root.right);

        boolean full = true;
        if (!left.full || !right.full) {
            full = false;
        }
        if (left.nodeCount != Math.pow(2, left.height) - 1) {
            full = false;
        }
        if (right.nodeCount != Math.pow(2, right.height) - 1) {
            full = false;
        }

        int nodeCount = left.nodeCount + right.nodeCount + 1;
        int height = Math.max(left.height, right.height) + 1;

        return new Info(full, nodeCount, height);
    }

    // 1. 左树是满二叉树
    // 2. 右树是满二叉树
    // 3. 左树的节点数 = 2^树高 - 1
    // 4. 右树的节点数 = 2^树高 - 1
    public static class Info {
        boolean full;
        int nodeCount;
        int height;

        public Info() {
        }

        public Info(boolean full, int nodeCount, int height) {
            this.full = full;
            this.nodeCount = nodeCount;
            this.height = height;
        }
    }
}
